package com.base.dynamicprograming;

/**
 * @ClassName: RobTwo
 * @Description: 213. 打家劫舍 II
 * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
 * <p>
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/house-robber-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: li
 * @Date: 2021/8/21 4:58 下午
 */
public class RobTwo {
    public int rob(int[] nums) {
        /**
         * 由于首位相连，所以分两种情况动态规划。
         * 1、[1,n-1] 不考虑第一个元素,动态规划
         * 2、[0,n-2] 不考虑最后元素,动态规划
         */
        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        return Math.max(dp(nums, 0, nums.length - 2), dp(nums, 1, nums.length) - 1);
    }

    public int dp(int[] nums, int start, int end) {
        int p = nums[start], q = Math.max(nums[start + 1], nums[start]);
        for (int i = start + 2; i <= end; i++) {
            int tmp = Math.max(q,p+nums[i]);
            p = q;
            q = tmp;
        }
        return q;

    }

    public int rob1(int[] nums) {

        if(nums.length == 0){
            return 0;
        }
        if(nums.length==1){
            return nums[0];
        }
        return Math.max(dp1(0,nums.length-1,nums),dp1(1,nums.length,nums));
    }

    public int dp1(int start,int end,int[] nums){
        int pre = 0;
        int q = nums[start];
        for(int i = start+1;i<end;i++){
            int tmp = Math.max(q,pre+nums[i]);
            pre = q;
            q = tmp;
        }
        return q;
    }
}
